%!TEX root = paper.tex

\begin{figure*}[t]
 \centering
 \subfloat[$\RePre$ and $\ReSke$ from full result.]
   {\label{fig:eg-proj-full}\input{figs/full.tikz}}
 \hfill
 \subfloat[$\RePreProx$ and $\ReSke$ from an approximate solution:
   {\protect\tikz \protect\fill[red] (.5ex,.5ex) circle (.5ex);}
   true positive;
   {\protect\tikz \protect\fill[gray] (.5ex,.5ex) circle (.5ex);}
   false positive;
   {\protect\tikz \protect\fill[black] (.5ex,.5ex) circle (.5ex);}
   false negative (all w.r.t.\ $\RePre$).]
   {\label{fig:eg-proj-sketch}\input{figs/sketch.tikz}}
 \caption{Projection query example on $(\texttt{points},
     \texttt{rebounds})$, visualized using 2d scatter plot for
     $\RePre$ and $\RePreProx$, on top of heatmap for $\ReSke$.
     In the heatmap, the weight of each point is distributed
     uniformly in its neighborhood.}\label{fig:eg-proj}
\end{figure*}

\section{Exploration Query Problem}
\label{sec:problem}
In this section, we introduce the basic notations (Section~\ref{sec:problem:prelim})
and formally define the problem (Section~\ref{sec:problem:defn}).
In Section~\ref{sec:problem:query}, we present three examples
of exploration queries that we study in this paper.
For readers' convenience, we summarize all notations in Table~\ref{table:notation}.

\begin{table}[t]
  \small\centering
  \begin{tabular}{|c|l|}
    \hline
    \textbf{Notation} & \textbf{Description} \\\hline
    \hline
    $\R_i$ & data for object $i$, as a sequence of tuples\\
    \hline
    $n_i$ & number of tuples in $\R_i$\\
    \hline
    $N$ & number of objects\\
    \hline
    $\DataSet$ & dataset, as a collection of data $\R_{1\dots N}$ for
        objects $1 \dots N$\\
    \hline
    $\|\DataSet\|$ & total number of tuples in $\DataSet$\\
    \hline
    $f$ & an exploration query\\
    \hline
    $\Result_f(\DataSet)$ & result of evaluating $f$ on $\DataSet$, as a
        multi-set of 2d points\\
    \hline
    $\Neighbor_\RR(p;r)$ & neighborhood of a 2d point $p$ given radius $r$\\
    \hline
    $\Neighbor_\Result(p;r)$ & neighbors of a 2d point $p$ in multi-set
        $\Result$ given radius $r$\\
    \hline
    $\RePre$ & points of $\Result$ in a sparse neighborhood\\
    \hline
    $\ReSke$ & a ``sketch'' of $\Result \setminus \RePre$, as a set of
        weighted 2d points\\
    \hline
    $r_x, r_y$ & neighborhood size\\
    \hline
    $\tau$ & neighborhood density threshold for points in $\RePre$\\
    \hline
  \end{tabular}
  \caption{Table of notations.}
  \label{table:notation}
\end{table}

 
\subsection{Preliminaries}
\label{sec:problem:prelim}
Suppose we have data $\DataSet$ for $N$ distinct objects as $N$
relations $\R_1,$ $\dots,\R_N$.  The data for object $i$, $\R_i=
(t_{i,1},\dots,t_{i,n_i})$, is an ordered set of $n_i$ tuples.
All tuples $t_{i,j}$ conform to the same schema $R$.  Let
$\|\DataSet\|=\sum_{i=1}^N n_i$ denote the total number of tuples
for all objects.

Let $f$ denote an \emph{exploration query} that takes input an
ordered set of tuples conforming to $R$, and outputs a (multi-)set
of points in $\RR$.  The result of evaluating $f$ on data $\DataSet
  = \{\R_1,\dots,\R_N\}$ is denoted by $\Result_f(\DataSet)$, or
simply $\Result$ when the context is clear.  $\Result_f(\DataSet)$
is defined as the bag of the results of evaluating $f$ on each
$\R_i$, i.e., $\Result_f(\DataSet)=\uplus_{i=1}^N f(\R_i)$, or
simply $\Result$ when the context is clear.
We formally define the \emph{neighborhood} of a point $p\in\RR$
as
\begin{equation*}\label{eq:nb-def}
 \Neighbor_{\RR}(p; r) = \{p' \in \RR \mid \|p-p'\| \le r\},
\end{equation*}
with the radius $r$ as an input.

The \emph{neighbors} of a point $p$ in a finite set $\Result$ is
denoted by 
\begin{equation*}
 \Neighbor_{\Result}(p; r) = \Neighbor_{\RR}(p; r) \cap \Result.
\end{equation*}

In the remainder of the paper, we use (scaled) $L_\infty$-norm for
$\|\cdot\|$ in the neighbor definition above, i.e.:
\begin{align*}
 \Neighbor_{\RR}(p; r_x, r_y) &=
   \{p' \in \RR \mid |p.x - p'.x| \le r_x \wedge |p.y - p'.y| \le r_y\};\\
 \Neighbor_{\Result}(p; r_x, r_y) &=
   \Neighbor_{\RR}(p; r_x, r_y) \cap \Result.
\end{align*}

However, the results of this paper extend to other commonly
used norms as well, e.g., $L_1$-norm, $L_2$-norm.

\subsection{Problem Definition}
\label{sec:problem:defn}
Given an exploration query $f$ on dataset $\DataSet$, our goal
is to efficiently generate the following two components for
visualizing $\Result_f(\DataSet)$.
\begin{itemize}
 \item $\RePre$: points of $\Result_f(\DataSet)$ in a sparse
   neighborhood (for scatter plot);
 \item $\ReSke$: a ``sketch'' of rest of the points, as a set
   of weighted points (for heatmap).
\end{itemize}

We define the \emph{sparse points} $\RePre$ as the set of points whose
number of neighbors is no more than some \emph{sparsity threshold}
$\tau$.  Given $r_x$ and $r_y$ that define the neighborhood of a point
and sparsity threshold $\tau$, all points with a sparse neighborhood
can be precisely identified.

For all the other points, i.e., $\Result \setminus \RePre$, we create
a \emph{sketch} $\ReSke$ (not to be confused with the concept of
sketch in data streams).  The sketch consists of a set of weighted
points, where $(p, w_p) \in \ReSke$ represents an estimated $w_p$
points of $\Result \setminus \RePre$ in $p$'s neighborhood.  A good
sketch should have each point of $\Result \setminus \RePre$
``covered'' by one point of $\ReSke$.  We use the \emph{sketch
  distance function} $\delta$, which will be defined later in this
section, to capture the quality of a sketch $\ReSke$ measured w.r.t.\
$\Result\setminus\RePre$.

The challenge in evaluating an exploration query comes with a
computation budget.  To serve the purpose of realtime exploration, we
would like to evaluate the query $f$ without performing the evaluation
on the full data of all objects.  With a limited amount of data
accesses, an approximate solution $(\RePreProx, \ReSke)$ needs to be
found.  The quality of $\RePreProx$ is measured by its precision and
recall w.r.t.\ $\RePre$, while the quality of $\ReSke$ is measured by
$\delta$ w.r.t.\ $\Result\setminus\RePre$.

Motivated by achieving as high quality as possible for both $\RePre$
and $\ReSke$ within a budget constraint, we formally define the
exploration query evaluation problem as follows.

\begin{definition}[Exploration Query Evaluation]\label{def:explore}
 With a relational schema $R$, a dataset of $N$ objects
 $\DataSet=\{\R_i\}_{i=1}^N$, the full result of an exploration
 query $f$ is given by $\Result=\uplus_{i=1}^N f(\R_i)$.
 
 Given neighborhood radius $r_x$, $r_y$, a sparsity threshold $\tau$,
 solve the following two tasks:
 \begin{itemize}
  \item \textbf{Task 1.} Find $\RePreProx$ that approximates the
    set of sparse point $\RePre \subseteq \Result$, where
    \[
     \RePre = \{p \in \Result \mid |\Neighbor_{\Result}(p; r_x, r_y)| \le \tau\}.
    \]
%   \item \textbf{Task 2.} Partition $\Result$ into $\Partition=
%     \set{\Partition_{ij}}_{i,j\in\Z}$, where partition
%     $\Partition_{ij}=\set{p\in\Result:p\in[ir_x,(i+1)r_x)\times
%     [jr_y, (j+1)r_y)}$. For each non-empty partition
%     $\Partition_{ij}$, find $|\Partition_{ij}-\RePre|$.
%     Define $\ReSke=\set{((i,j),|\Partition_{ij}-\RePre|)}$
  \item \textbf{Task 2.} Find a weighted point set
    \[
     \ReSke = \{(p, w_p) \mid p \in \Result \wedge w_p \in \Z^+\}
    \]
    that minimizes $\delta(\Result\setminus\RePre, \ReSke)$.
%    such that $\delta(\Result \setminus \RePre, \ReSke) = 0$.
 \end{itemize}
 subject to a given computation budget $\eta\in(0,1]$ such that at
 most $\eta\cdot \|\DataSet\|$ tuples can be accessed during
 evaluation.
\end{definition}

\paragraph{Sketch Distance.}
The distance function $\delta$ measures the quality
of the sketch $\ReSke$ w.r.t.\ $\Result\setminus\RePre$ and needs
to capture two aspects of sketch quality:
\begin{itemize}
 \item[I.] the \emph{distribution} of $\ReSke$ should resemble that
   of $\Result\setminus\RePre$;
 \item[II.] the \emph{magnitude} of $\ReSke$ should be close to that
   of $\Result\setminus\RePre$.
\end{itemize}
% The standard EMD captures (I) but not (II).  Therefore, we introduce
% the following adaption.

\begin{definition}[Sketch Distance]\label{def:dist}
 Given a multiset of points $P = \{p_1, p_2, \dots, p_n\}$ and a
 weighted point set $Q = \{(q_1, w_1), (q_2, w_2),$ $\dots, (q_m,
   w_m)\}$,
%    Let the \emph{ground distance} be
%  \[
%    d_{ij} = \begin{cases}
%              0 & \text{if } p_j \in \Neighbor_{\RR}(q_i; r_x, r_y)\\
%              1 & \text{otherwise}
%             \end{cases}
%  \]
   the \emph{sketch distance}\footnote{The sketch distance is adapted
     from the Earth Mover's
     Distance~\cite{cv98-RubnerTomasiGuibas-emd} widely used in
     measuring the dissimilarity between two images in image
     processing.  Adaptations are made to suit the purpose of this
     work.} between $P$ and $Q$ is defined as
 \[
   \delta(P, Q) = 1 - \frac{\mathsf{OPT}}{\max\{|P|, \|Q\|\}},
 \]
 where $\|Q\| = \sum_{j = 1}^m w_j$ and $\mathsf{OPT}$ is the optimal
 solution to the following integer program:
 \begin{alignat}{2}
   \text{maximize }   & \sum_{i=1}^m \sum_{j=1}^n x_{ij} \mathbf{1}[p_j \in \Neighbor_{\RR}(q_i; r_x, r_y)],\\
   \text{subject to } & \sum_{j=1}^n x_{ij} \leq w_i ,\  1\leq i\leq m \label{eqn:ip-req1} \\
                      & \sum_{i=1}^n x_{ij} \leq 1   ,\  1\leq i\leq n \label{eqn:ip-req2} \\
                      & x_{ij} \in \{0, 1\}          ,\  1\leq j\leq n,\ 1\leq i\leq m.\label{eqn:ip-req3}
%                       & \mathbbm{1}x_{ij}\{\begin{array}{ll}
%                                  \in \{0, 1\} & \text{if } p_j \in \Neighbor_{\RR}(q_i; r_x, r_y)\\
%                                  = 0          & \text{otherwise}
%                                 \end{array}
%                        &,\ & 1\leq j\leq n,\ 1\leq i\leq m
 \end{alignat}
\end{definition}

Consider $P$ as the set of points to be sketched, i.e.,
$\Result \setminus \RePre$, and the weighted point set $Q$ as the
sketch.  A point $(q, w)\in Q$ can cover a point $p \in P$ if $p$ and
$q$ are neighbors, and $q$ can cover at most $w$ points in $P$.  On
the other hand, each point of $p$ can be covered by at most one point
of $Q$.  Hence, $\mathsf{OPT}$ is the maximum number of points of $P$
that $Q$ can cover.

The quantity $\frac{\mathsf{OPT}}{\max\{|P|, \|Q\|\}}$ measures the
similarity between $P$ and sketch $Q$.  Dividing by the larger of
$|P|$ and $\|Q\|$ penalizes possible disparity between them.

Let us revisit Kevin Love's 31-\textsf{point}, 31-\textsf{rebound}
game example.  Consider the performance of all NBA players in all
games in terms of \textsf{point}-\textsf{rebound}, and visualize all
points ($\approx$$10^6$ of them) by combining $\RePre$ and
$\ReSke$.\footnote{We set $r_x=r_y=2$ and $\tau=16$ such that $\RePre$
  contains roughly 100 points so that human eye can perceive.}  In
Figure~\ref{fig:eg-proj-full}, points of $\RePre$ are plotted as red
dots.  $\ReSke$ is visualized using heatmap, by distributing the
weight of each point evenly in its neighborhood.  Here, $\RePre$
and $\ReSke$ are produced using an expensive baseline algorithm
(Algorithm~\ref{algo:base}), which performs full evaluation on the
entire dataset $\DataSet$ and guarantees
$\delta(\Result\setminus\RePre, \ReSke) = 0$.

On the other hand, Figure~\ref{fig:eg-proj-sketch} visualizes, in the
same way, approximated sets $\RePreProx$ and $\ReSke$ produced by
Algorithm~\ref{algo:sample}, which accesses only 20\% tuples of the
entire dataset, with the projection query passed in as a blackbox
function.  To compare with the visualization on the full result, we
show false positives and false negatives of $\RePreProx$ 
w.r.t.\ $\RePre$ as grey and black dots, respectively.  It is obvious
in both Figure~\ref{fig:eg-proj-full} and \ref{fig:eg-proj-sketch}
that Love's 31-\textsf{point}, 31-\textsf{rebound} performance
was impressive, being far from the vast majority of all points.  One
can also see the resemblance between the two figures, even though
Figure~\ref{fig:eg-proj-sketch} incurs significantly fewer
data accesses and hence much lower latency.

% 
% In the integer program in Definition \ref{def:emd}, Constraint
% \ref{eqn:ip-req1} states that at most $w_i$ points of $P$ can be
% assigned to $q_i$.  Constraint \ref{eqn:ip-req2} states that each
% point of $P$ is assigned to at most one point of $Q$.  In the
% objective function, the reward of assigning $p_j$ to $q_i$ is 1
% if $p_j$ is in the neighborhood of $q_i$, and otherwise 0.

% Note that there are two differences between Definition \ref{def:emd}
% and the standard Earth Mover's Distance
% \cite{cv98-RubnerTomasiGuibas-emd}.  First, the standard EMD would
% have $\sum_{i=1}^m\sum_{j=1}^n x_{ij} d_{ij}$ as \emph{minimization}
% objective in the integer program.  Suppose the optimal solution there
% would be $\mathsf{OPT}^\star$.  It is not hard to see that
% $\mathsf{OPT} + \mathsf{OPT}^\star = \min\{|P|,\|Q\|\}$.
% \footnote{This is due to the choice of the \emph{ground distance}
%   function $d$.  Using other distance functions, e.g. L-norms, would
%   void this property.  On the other hand, this 0-1 valued ground
%   distance function $d$ is coherent with the thresholded definition
%   for neighborhood.}
% Second, standard EMD would have $\delta(P,Q)=\tfrac{\mathsf{OPT}
%   ^\star}{\min\{|P|,\|Q\|\}} = 1-\tfrac{\mathsf{OPT}}{\min\{|P|,
%   \|Q\|\}}$.  The use of the $\min$ function would mean that any
% mismatch between the sizes of $P$ of $Q$ would not be penalized.
% \footnote{Consider an extreme case where $P$ is large, but $Q$ has
%   only one point, which is also in $P$, or in the neighborhood of
%   some point of $P$.  $\delta(P,Q)$ would be undesirably evaluated
%   to $0$ if defined using $\min$.  In contrast, $\delta(P,Q)$, as
%   expected, is close to $1$ using $\max$.}
% Therefore, we use $\max$ instead.
% 
% We do not require $\|Q\|$ to be equal to $|P|$ for two reasons.
% First, the full solution $\Result$ is unavailable due to computation
% budget, thus $|\Result|$ being unavailable as well.  Second, as will
% be shown in earlier sections, our algorithm is oblivious to the
% problem definition, thus unaware of the optimization objective.
% \footnote{One may have been concerned that the chosen ground
%   distance function $d_{ij}$ is not a metric, resulting in the
%   adapted EMD being non-metric.  But since the other necessary
%   condition, i.e. $\|Q\|=|P|$, for an EMD to be a metric cannot
%   be enforced here, using a metric $d_{ij}$ would not make a
%   difference.}
% \footnote{The IP in the definition of \emph{adapted EMD} can be
%   transformed into an instance of the max flow problem, and therefore
%   solved in time polynomial in $|P|$ and $|Q|$.  But this is only a
%   concern in the efficiency of evaluation, not the algorithm itself.
%   Therefore it is beyond the scope of this paper.}

\subsection{Query Types}
\label{sec:problem:query}

We study the following three types of exploration queries commonly
made on sports data. In Section~\ref{sec:expr:data}, we also show
applications to two other domains, the \emph{Computer Science
  bibliography} and the \emph{Wikipedia edit history}.

\begin{itemize}
 \item[I.] \textbf{Projection Query.} Given numerical
   attributes $A,B\in R$,
   \[
    f(\R) = \{(t.A, t.B) \mid t \in \R \}.
   \]
   An example application of the projection query would be to find a
   player's point-rebound stats in every game; i.e.,
   $(A,B) = (\texttt{points}, \texttt{rebounds})$.  When $f$ is
   applied to Kevin Love, one of the result 2d points would be
   $(31, 31)$, which corresponds to ``Kevin Love's 31-point,
   31-rebound game.''
 \item[II.] \textbf{Count Query.} Given numerical attribute $A\in R$,
   \[
    f(\R) = \{(v, c) \mid v \in \R.A \wedge c = |\{t \in \R \mid
      t.A\ge v\}|\}.
   \]
   For example, Michael Jordan's 38 games with 50 or more points (most
   in NBA
   history\footnote{\url{www.nba.com/jordan/list_50games.html}}) maps
   to a 2d point $(50, 38)$ when evaluating a count query on Jordan's
   game-by-game stats data with $A = \texttt{points}$.  Note that $f$
   can return multiple points for Michael Jordan, with lower point
   values associated with higher count values.
 \item[III.] \textbf{Streak Query.} Given numerical attribute
   $A\in R$,
   \begin{gather*}
    f(\R) = \text{Pareto optimal subset of }\{(v, \mathsf{len} =
      r-l+1) \mid \\ %\nonumber 
    1\le l\le r\le n_\R~\wedge~v = \min_{l\le i\le r}t_i.A\}. %\nonumber
   \end{gather*}
   This is known as the set of \emph{prominent streaks} in sequence
   $\R.A$~\cite{sigkdd11-JiangLiEtAl-prominent_streak}.  For
   instance, LeBron James's 9-game 35-or-more-points streak is
   represented by a 2d point $(35, 9)$ in the result set of
   evaluating a streak query on James' stats (with $A=\texttt{points}$).
%  \item[IV.] \textbf{Span Aggregation Query.} Given numerical
%    attribute $A\in R$,
%    \[
%     f(\R)=\{(\mathsf{len}, v) \mid v = \max_{0\le i\le n_\R - 
%       \mathsf{len}} g(t_{i+1}, \dots, t_{i + len})\}, 
%    \]
%    where function $g$ can be sum, max, min, etc.  Here is an
%    example of the span aggregation query, ``Danny Green has
%    made 16 three-point field goals in his first three career
%    NBA Finals games''\footnote{\url{http://espn.go.com/espn/
%    elias?date=20130612}}.  This example statement is represented
%    by point $(3, 16)$ in the result set of evaluating a span
%    aggregation query on Green's stats with $A = \texttt{three-point
%    field goals}$ and $g$ being simple summation.
\end{itemize}
While these three types of exploration queries are represented by very
different functions $f$, they share one common characteristic---same
formats of input (a relation conforming to schema $R$) and output (a
set of points in $\RR$).  In the rest of the paper, we illustrate our
algorithms using these query types.
